package com.lyt.springboot.util.algorithm;

import java.util.Arrays;

public class Offer_35 {
    /**
     * 思路
     * 1.先无限二分
     * 2.排序
     */
    int count = 0;
    int mod= 1000000007;
    public int reverse(int[] data) {
        sort(data);
        return count % mod;
    }

    private int[] sort(int[] data) {
        if(data.length==1) {
            return data;
        }
        int mid  = data.length/2;
        int[] left = sort(Arrays.copyOfRange(data,0,mid));
        int[] right = sort(Arrays.copyOfRange(data,mid,data.length));
        int[] result = merge(left,right);
        return result;

    }
    private  int[] merge(int[]left ,int[]right) {
        int[] result = new int[left.length+ right.length];
        int i = 0;
        int j = 0;
        int p = 0;

        while(i< left.length && j< right.length) {
            if(left[i]<right[j]) {
                result[p] = left[i];
                i++;

            }else {
                result[p] = right[j];
                 // 【3】 4 5  【1】 2 6
                //这里关注一下！
                //取上述当左边都大于右边的部分 ！！
               count += left.length-i;
                j++;
            }
            p++;

        }
        while(i< left.length) {
         result[p++] = left[i++];
        }
        while(j<right.length) {
            result[p++] = right[j++];
        }
        return result;
    }

    public static void main(String[] args) {
        int[] array = {7,5,6,4};
        Offer_35 offer = new Offer_35();
        int result = offer.reverse(array);
        System.out.println(result);
    }

}
